The Internet is a shared communication medium, whose resources every user has the opportunity to use. Its value chain now involves a strong diversity of stakeholders, some of whom can have conflicting interests in the way the shared resources are managed. This state of affairs has been exacerbated by the network neutrality debate over the past few years. At the technical level, the debate boils down to assessing which control mechanisms are adequate for network operators to employ to mitigate the impact of some customers' heavy usage so that usage doesn't cause a deterioration in the network service every other customer can get from the connectivity product they have subscribed to. Insomuch as it is possible, it is important that such policing mechanisms should deal with the physical impact of a customer's traffic on the network, rather than its nature.
At the moment most network operators have defined “fair usage” policies which specify the traffic limits to which customers will be subjected, based on the product they have subscribed to. This can include a specific upper limit for the amount of peer-to-peer traffic that can be generated at peak hours: peer-to-peer traffic can indeed very easily take over disproportionate amounts of access bandwidth because of the way peer-to-peer applications have been designed.
However that approach is of limited efficiency: it assumes that all traffic using a known protocol (which on average causes congestion in the network) is responsible for increases in congestion, and that only that traffic is responsible for that congestion. If a new peer-to-peer application was designed that only uses uncongested network path links to operate, it would be penalised as much as any other peer-to-peer traffic application. On the other hand, heavy, live multimedia exchanges across congested links might hardly be affected by traditional policing techniques but could still contribute disproportionately to network congestion.
Based on the economics of networks, it has been shown (see [Kelly98] for example) that controlling the congestion a customer creates is a much better way to ensure the efficient usage of a shared resource than controlling the raw amount of traffic the customer generates. Congestion pricing is a way to ensure users are held accountable for the amount of congestion they create. However, users are wary of being exposed to such dynamic variation of prices as could occur with prices based on network congestion.
It has been advocated (see [Briscoe07]) that using congestion capping would present substantially similar advantages to using congestion pricing, while avoiding exposing users directly to dynamic congestion prices.
Re-Feedback
The re-feedback framework has been developed to allow for customers' usage to be accounted for based on the congestion externality they cause to other users. It will be understood that one of the functions of the Internet Protocol (IP) header is to carry path information from a sender to a receiver. This path information allows downstream nodes (nodes nearer the receiver) to learn about the upstream state of the path. Mechanisms exist which allow the receiver to feed this information back to the sender. The re-feedback proposal (see [Briscoe05c] for example) provides a mechanism whereby path information that a receiver feeds back to a sender can be re-inserted into the forward data path, thus allowing nodes along the path to learn information relating to the downstream state or the path as well as information about the upstream state of the path.
International patent applications WO 2005/096566 and WO 2005/096567 relate to data networks, and to nodes making up parts of data networks, arranged to derive information relating to the characterisation of paths taken by data travelling between nodes in the networks according to the re-feedback proposal.
Congestion Signalling and Responses Thereto
It will be understood that data traversing the Internet follows a path between a series of routers, controlled by various routing protocols. Each router seeks to move packets closer to their final destination. If too much traffic traverses the same router in the network, the router can become congested and packets start to experience excessive delays whilst using that network path. If sources persist in sending traffic through that router it could become seriously overloaded (congested) and even drop traffic (when its buffers overflow). If sources still persist in sending traffic around this bottleneck it could force more routers to become congested, and if the phenomenon keeps spreading, that can lead to a congestion collapse for the whole Internet—which occurred regularly in the mid-eighties.
A solution to that problem has been to ensure that sources take responsibility for the rate at which they send data over the Internet by implementing congestion control mechanisms. According to these mechanisms, sources are required to monitor path characterisation metrics to detect when the path their data is following is getting congested, in which case they react by reducing their throughput. In the absence of such congestion indications, they may slowly increase their throughput. The congestion level is one of the parameters controlling the rate adaptation of a source sending data over a congested path.
The congestion level can be signalled either implicitly (through congested routers dropping packets when their buffers overflow or to protect themselves) or explicitly (through mechanisms such as explicit congestion notification—see next subsection). Currently the most common option is implicit signalling. Historically, routers would drop packets when they got completely saturated (which happens when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called “Droptail”. Random Early Detection (RED) (see [RED]) is an improvement where routers monitor the average queue length in their buffer and when the average queue is higher than a given threshold, the router starts to drop packets with a probability which increases with the excess length of the queue over the threshold. It is widely used in today's Internet because it allows sources to react more promptly to incipient congestion. Sources using Transmission Control Protocol (TCP) are able to detect losses, because a packet loss causes a gap in the sequence; whenever a TCP source detects a loss, it is meant to halve its data transmission rate, which should alleviate the congestion on the router at the bottleneck.
Explicit Congestion Notification
Explicit Congestion Notification (ECN) (see [ECN]) further improves on RED by using a two-bit ECN field in the IP header to signal congestion. It runs the same algorithm as RED, but instead of dropping a packet, it sets its ECN field to the Congestion Experienced (CE) codepoint. The ECN standard requires a sender to echo any congestion mark signalled in the data; for instance, a TCP receiver sets the Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets as if a packet has been dropped for the purpose of its rate control. In turn the source then reacts to the congestion by halving its transmission rate and notifies the receiver of this using the Congestion Window Reduced (CWR) codepoint.
The four values of the two-bit ECN field in the IP header are:                Non ECT, which signifies that the packet belongs to a flow that doesn't support ECN.        ECT(0) and ECT(1), which signify that the packet belongs to a flow that supports ECN but that upstream routers haven't had to mark the packet.        Congestion Experienced (CE), which signals that a packet has experienced incipient congestion.        
It will be understood that allowing a sender to initially assign either of two different codepoints (i.e. “ECT(0)” and “ECT(1)”) to a packet enables the sender to detect if network elements are fraudulently erasing CE codepoints. If a packet which has experienced congestion and therefore has been marked with a “CE” codepoint subsequently has that CE codepoint removed in an attempt to hide the indication that the packet has experienced congestion, this will be detectable by the sender unless the CE codepoint has been changed back to the correct one of the two possible initial codepoints. This is discussed further in [RFC3540].
Congestion Policing
International patent application WO 2006/082443, which is further discussed in [Jacquet08], and related European patent application EP 1,758,313 (from which WO 2006/082443 claims priority) relate to methods and apparatus for policing the congestion responsiveness of individual flows (rather than that of a customer). They disclose methods and apparatus for policing flow in a data network by determining a measure of greediness of a flow through a node, comparing said measure of greediness with a measure indicative of acceptable greediness dependent on the expected greediness of a compliant flow experiencing substantially similar path conditions, and designating the flow for possible sanction in the event that the greediness is not in accordance with said acceptable greediness.
Mechanisms have since been proposed which use concepts based on the re-feedback proposal, and promote the use of congestion cap with connectivity products.
Re-ECN (see [Briscoe09a]) is an example of a system that utilises the re-feedback concept, whereby path information that a receiver feeds back to a sender can be “re-inserted” into the forward data path, in order to provide upstream and downstream congestion information throughout the network. With re-ECN, the information “re-inserted” is based on ECN marks in previously transmitted packets. It is similar to ECN but uses an extra bit in the packet header. This bit enables a number of new codepoints to be used. A simple way to understand the re-ECN protocol is to think of each packet as having a different colour flag (corresponding to a codepoint). At the start of a flow, a green flag (FNE or “feedback not established”) is used to indicate that a sender doesn't have existing knowledge of the path. Green flags are also used when the sender is unsure about the current state of the path. By default packets are marked with grey flags. If they encounter congestion during their progress through the network they are marked with a red flag. The destination will send back a count of the number of red flags it has seen. For every red flag it is informed of, the sender should send a packet with a black flag (re-echo). These black flags cannot be modified once they are set by the sender, so signal to a node at any point on the path what the total end-to-end congestion is expected to be (based on the fact that the number of black flags signals the total end-to-end congestion level actually experienced by the immediate predecessors of the current packets). At any intermediate node the upstream congestion is given by the number of red flags seen, and the downstream congestion may therefore be derived by the difference between the number of red flags and the number of black flags.
Mechanisms based on the concept referred to as “re-ECN” are discussed in [Briscoe09a]. A related Internet Draft, referred to as [Briscoe09b], discusses the motivation for deploying such mechanisms. It provides examples of mechanisms that can use the re-ECN protocol to ensure that data sources respond correctly to congestion, and examples of mechanisms that are able to ensure that the dominant selfish strategy of both network domains and end-points will be to use the protocol honestly.
One such mechanism proposed in [Briscoe09a], which will be explained with reference to FIG. 1, consists of using a basic token bucket which is operated based on the amount of congestion a user creates on the network, rather than the volume of traffic it generates. Such a mechanism is therefore referred to as a “Congestion Policer”, rather than a “Rate Policer”.
As illustrated in FIG. 1, the token bucket 11 is filled at a constant rate, and emptied in proportion to the contribution of the user's traffic to network congestion. First, when a packet 15 arrives at the policing node, the token reserve r is updated (step s110). This updating involves two factors: the token reserve r is updated by adding tokens in proportion to a predetermined congestion allowance wLT of the user (step s110a). The token reserve r is also updated by removing tokens (step s110b) according to a function g( ) whose value depends on information retrieved from the packet header, in particular the size si and the re-ECN field (which reflects a congestion level pi). The function g( ) could be defined as:
g(packet) = siif the re-ECN codepoint signals a markg(packet) = 0otherwise
Subsequently, the packet is sanctioned (step s120) according to the relevant policy 12 with a probability f(r) where the sanction curve f( ) is null so long as the value of the token reserve r remains positive.
Such a mechanism puts an upper bound on the amount of congestion a user can cause in the long term. However one of the limitations of the mechanism is that it allows a user to create bursts of congestion. If the user has remained inactive for a long period of time, tokens will accumulate in the token bucket during such a period. If the user then becomes active again, it can consume the token reserve at a very quick pace, which could push congestion levels at bottlenecks to critical levels for at least a short period of time. This effect is illustrated in FIG. 2: even if the token reserve a user can accumulate is limited to a maximum level b (symbolised by the area shown as “surface b” on the graph, which can be regarded as indicating an agreed maximum amount of the user's “congestion allowance” that the user can hold in reserve in order to enable its future traffic that has already contributed to congestion still to be forwarded in the normal manner), if the user consumes that token reserve over a short period of time Tburst, then it can cause a spike of congestion kpeak in proportion to b/Tburst.
Protection against this is possible by setting a tight limit to the depth of the bucket b, thus limiting the potential amount of congestion of a future burst, however this would be very restrictive for users who only use their network congestion sporadically.
Other Known Techniques
Mechanisms to police data rates over two time-scales have been proposed. For instance the Weighted Random Early Detection (WRED) proposal (see [WRED]) proposes a dual token bucket to limit the throughput of a user to a Committed Information Rate (CIR) in the long-term, and a Peak Information Rate (PIR) bucket in the short-term, which allows for manageable bursts of traffic. It will be noted, however, that this mechanism deals only with traffic throughput.